package bTree.LeetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.stream.Collectors;

public class 去除重复字母 {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Integer> map = new HashMap<>();  //记录次数来看是不是最后出现的
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }
        stack.add(s.charAt(0));
        map.put(s.charAt(0), map.get(s.charAt(0)) - 1);
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.get(c) - 1);
            if (!stack.contains(c)) {
                while (!stack.isEmpty() && c <= stack.peek() && map.get(stack.peek()) > 0) {
                    stack.pop();
                }
                stack.add(c);
            }

        }
        return stack.stream()
                .map(Object::toString) // 每个元素转为字符串
                .collect(Collectors.joining()); // 无分隔符拼接
    }
}